﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;


namespace www.interviewstreet.com.GoingOffice
{
    class Program
    {

        private static int totalNodes = 100000;
        private static Dictionary<int, Dictionary<int, int>> cost;
        private static DijkstraFast dijkstra;
        private static int costTotal;
        

        static void Main(string[] args)
        {

            int N, M;
            string[] a = Console.ReadLine().Split(' ');
            N = Convert.ToInt32(a[0]);
            M = Convert.ToInt32(a[1]);
            costTotal = 0;
            cost =  new Dictionary<int, Dictionary<int, int>>();
            
            // initialize the cost matrix
            for (int i = 0; i < M; i++)
            {
                cost[i] = new Dictionary<int, int>();
            }

            string[] temp;


            for (int i = 0; i < M; i++)
            {
                temp = Console.ReadLine().Split(' ');
                cost[Convert.ToInt32(temp[0])].Add(Convert.ToInt32(temp[1]), Convert.ToInt32(temp[2]));
                cost[Convert.ToInt32(temp[1])].Add(Convert.ToInt32(temp[0]), Convert.ToInt32(temp[2]));

            }

            dijkstra = new DijkstraFast(N,
                                            new DijkstraFast.InternodeTraversalCost(getInternodeTraversalCost),
                                            new DijkstraFast.NearbyNodesHint(GetNearbyNodes));

            int destination, source;
            temp = Console.ReadLine().Split(' ');
            source = Convert.ToInt32(temp[0]);
            destination = Convert.ToInt32(temp[1]);

            int Q;
            Q = Convert.ToInt32(Console.ReadLine());


            List<Blockage> blockages = new List<Blockage>();
            for (int i = 0; i < Q; i++)
            {
                temp = Console.ReadLine().Split(' ');
                blockages.Add(new Blockage(Convert.ToInt32(temp[0]), Convert.ToInt32(temp[1])));

            }
            List<float> r= new List<float>();
            foreach (var blockage in blockages)
            {
                int tempV = cost[blockage.U][blockage.V];
                cost[blockage.U].Remove(blockage.V);
                cost[blockage.V].Remove(blockage.U);
                int[] x = dijkstra.GetMinimumPath(source, destination);
                r.Add(dijkstra.distance[source]);
                cost[blockage.U].Add(blockage.V, tempV);
                cost[blockage.V].Add(blockage.U,tempV);
                //graph[blockage.U][blockage.V] = tempV;

            }
            r.ForEach(p=>Console.WriteLine("{0}",p));
            

            
        }

        // get costs. If there is no connection, then cost is maximum.
        private static float getInternodeTraversalCost(int start, int finish)
        {
            
            return cost[start][finish];
        }

        private static IEnumerable<int> GetNearbyNodes(int startingNode)
        {
            List<int> nearbyNodes = new List<int>(4);

            foreach (KeyValuePair<int, int> node in cost[startingNode])
            {
                nearbyNodes.Add(node.Key);
            }

            
            return nearbyNodes;
        }

        // a function to get relative position from one node to another
        private static int GetRelativePosition(int start, int finish)
        {
            if (start - 1 == finish)
                return 0;

            else if (start + 1 == finish)
                return 1;

            else if (start + 5 == finish)
                return 2;

            else if (start - 5 == finish)
                return 3;

            return -1;
        }


    }



    public interface IPriorityQueue : ICollection, ICloneable, IList
    {
        int Push(object O);
        object Pop();
        object Peek();
        void Update(int i);
    }
    public class BinaryPriorityQueue : IPriorityQueue, ICollection, ICloneable, IList
    {
        protected ArrayList InnerList = new ArrayList();
        protected IComparer Comparer;

        #region contructors
        public BinaryPriorityQueue()
            : this(System.Collections.Comparer.Default)
        { }
        public BinaryPriorityQueue(IComparer c)
        {
            Comparer = c;
        }
        public BinaryPriorityQueue(int C)
            : this(System.Collections.Comparer.Default, C)
        { }
        public BinaryPriorityQueue(IComparer c, int Capacity)
        {
            Comparer = c;
            InnerList.Capacity = Capacity;
        }

        protected BinaryPriorityQueue(ArrayList Core, IComparer Comp, bool Copy)
        {
            if (Copy)
                InnerList = Core.Clone() as ArrayList;
            else
                InnerList = Core;
            Comparer = Comp;
        }

        #endregion
        protected void SwitchElements(int i, int j)
        {
            object h = InnerList[i];
            InnerList[i] = InnerList[j];
            InnerList[j] = h;
        }

        protected virtual int OnCompare(int i, int j)
        {
            return Comparer.Compare(InnerList[i], InnerList[j]);
        }

        #region public methods
        /// <summary>
        /// Push an object onto the PQ
        /// </summary>
        /// <param name="O">The new object</param>
        /// <returns>The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.</returns>
        public int Push(object O)
        {
            int p = InnerList.Count, p2;
            InnerList.Add(O); // E[p] = O
            do
            {
                if (p == 0)
                    break;
                p2 = (p - 1) / 2;
                if (OnCompare(p, p2) < 0)
                {
                    SwitchElements(p, p2);
                    p = p2;
                }
                else
                    break;
            } while (true);
            return p;
        }

        /// <summary>
        /// Get the smallest object and remove it.
        /// </summary>
        /// <returns>The smallest object</returns>
        public object Pop()
        {
            object result = InnerList[0];
            int p = 0, p1, p2, pn;
            InnerList[0] = InnerList[InnerList.Count - 1];
            InnerList.RemoveAt(InnerList.Count - 1);
            do
            {
                pn = p;
                p1 = 2 * p + 1;
                p2 = 2 * p + 2;
                if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner
                    p = p1;
                if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
                    p = p2;

                if (p == pn)
                    break;
                SwitchElements(p, pn);
            } while (true);
            return result;
        }

        /// <summary>
        /// Notify the PQ that the object at position i has changed
        /// and the PQ needs to restore order.
        /// Since you dont have access to any indexes (except by using the
        /// explicit IList.this) you should not call this function without knowing exactly
        /// what you do.
        /// </summary>
        /// <param name="i">The index of the changed object.</param>
        public void Update(int i)
        {
            int p = i, pn;
            int p1, p2;
            do	// aufsteigen
            {
                if (p == 0)
                    break;
                p2 = (p - 1) / 2;
                if (OnCompare(p, p2) < 0)
                {
                    SwitchElements(p, p2);
                    p = p2;
                }
                else
                    break;
            } while (true);
            if (p < i)
                return;
            do	   // absteigen
            {
                pn = p;
                p1 = 2 * p + 1;
                p2 = 2 * p + 2;
                if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner
                    p = p1;
                if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
                    p = p2;

                if (p == pn)
                    break;
                SwitchElements(p, pn);
            } while (true);
        }

        /// <summary>
        /// Get the smallest object without removing it.
        /// </summary>
        /// <returns>The smallest object</returns>
        public object Peek()
        {
            if (InnerList.Count > 0)
                return InnerList[0];
            return null;
        }

        public bool Contains(object value)
        {
            return InnerList.Contains(value);
        }

        public void Clear()
        {
            InnerList.Clear();
        }

        public int Count
        {
            get
            {
                return InnerList.Count;
            }
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return InnerList.GetEnumerator();
        }

        public void CopyTo(Array array, int index)
        {
            InnerList.CopyTo(array, index);
        }

        public object Clone()
        {
            return new BinaryPriorityQueue(InnerList, Comparer, true);
        }

        public bool IsSynchronized
        {
            get
            {
                return InnerList.IsSynchronized;
            }
        }

        public object SyncRoot
        {
            get
            {
                return this;
            }
        }
        #endregion
        #region explicit implementation
        bool IList.IsReadOnly
        {
            get
            {
                return false;
            }
        }

        object IList.this[int index]
        {
            get
            {
                return InnerList[index];
            }
            set
            {
                InnerList[index] = value;
                Update(index);
            }
        }

        int IList.Add(object o)
        {
            return Push(o);
        }

        void IList.RemoveAt(int index)
        {
            throw new NotSupportedException();
        }

        void IList.Insert(int index, object value)
        {
            throw new NotSupportedException();
        }

        void IList.Remove(object value)
        {
            throw new NotSupportedException();
        }

        int IList.IndexOf(object value)
        {
            throw new NotSupportedException();
        }

        bool IList.IsFixedSize
        {
            get
            {
                return false;
            }
        }

        public static BinaryPriorityQueue Syncronized(BinaryPriorityQueue P)
        {
            return new BinaryPriorityQueue(ArrayList.Synchronized(P.InnerList), P.Comparer, false);
        }
        public static BinaryPriorityQueue ReadOnly(BinaryPriorityQueue P)
        {
            return new BinaryPriorityQueue(ArrayList.ReadOnly(P.InnerList), P.Comparer, false);
        }
        #endregion
    }
    public struct HeapNode
    {
        public HeapNode(int i, float w)
        {
            index = i;
            weight = w;

        }
        public int index;
        public float weight;
    }
    class BasicHeap
    {
        private List<HeapNode> InnerList = new List<HeapNode>();

        public BasicHeap() { }

        public int Count
        {
            get
            {
                return InnerList.Count;
            }
        }

        public void Push(int index, float weight)
        {
            int p = InnerList.Count, p2;
            InnerList.Add(new HeapNode(index, weight)); // E[p] = O
            do
            {
                if (p == 0)
                    break;

                p2 = (p - 1) >> 1;
                if (InnerList[p].weight < InnerList[p2].weight)
                {
                    HeapNode h = InnerList[p];
                    InnerList[p] = InnerList[p2];
                    InnerList[p2] = h;

                    p = p2;
                }
                else
                    break;
            } while (true);
        }

        public int Pop()
        {
            HeapNode result = InnerList[0];
            int p = 0, p1, p2, pn;
            InnerList[0] = InnerList[InnerList.Count - 1];
            InnerList.RemoveAt(InnerList.Count - 1);
            do
            {
                pn = p;
                p1 = (p << 1) + 1;
                p2 = (p << 1) + 2;
                if (InnerList.Count > p1 && InnerList[p].weight > InnerList[p1].weight)
                    p = p1;
                if (InnerList.Count > p2 && InnerList[p].weight > InnerList[p2].weight)
                    p = p2;

                if (p == pn)
                    break;

                HeapNode h = InnerList[p];
                InnerList[p] = InnerList[pn];
                InnerList[pn] = h;

            } while (true);
            return result.index;
        }
    }
    public class DijkstraFast
    {
        public  float[] distance;
        /// <summary> 
        /// An optional delegate that can help optimize the algorithm 
        /// by showing it a subset of nodes to consider. Very useful 
        /// for limited connectivity graphs. (like pixels on a screen!) 
        /// </summary> 
        /// <param name="startingNode"> 
        /// The node that is being traveled away FROM. 
        /// </param> 
        /// <returns> 
        /// An array of nodes that might be reached from the  
        /// <paramref name="startingNode"/>. 
        /// </returns> 
        public delegate IEnumerable<int> NearbyNodesHint(int startingNode);
        /// <summary> 
        /// Determines the cost of moving from a given node to another given node. 
        /// </summary> 
        /// <param name="start"> 
        /// The node being moved away from. 
        /// </param> 
        /// <param name="finish"> 
        /// The node that may be moved to. 
        /// </param> 
        /// <returns> 
        /// The cost of the transition from <paramref name="start"/> to 
        /// <paramref name="finish"/>, or <see cref="Int32.MaxValue"/> 
        /// if the transition is impossible (i.e. there is no edge between  
        /// the two nodes). 
        /// </returns> 
        public delegate float InternodeTraversalCost(int start, int finish);

        /// <summary> 
        /// Creates an instance of the <see cref="Dijkstra"/> class. 
        /// </summary> 
        /// <param name="totalNodeCount"> 
        /// The total number of nodes in the graph. 
        /// </param> 
        /// <param name="traversalCost"> 
        /// The delegate that can provide the cost of a transition between 
        /// any two nodes. 
        /// </param> 
        /// <param name="hint"> 
        /// An optional delegate that can provide a small subset of nodes 
        /// that a given node may be connected to. 
        /// </param> 
        public DijkstraFast(int totalNodeCount, InternodeTraversalCost traversalCost, NearbyNodesHint hint)
        {
            if (totalNodeCount < 3) throw new ArgumentOutOfRangeException("totalNodeCount", totalNodeCount, "Expected a minimum of 3.");
            if (traversalCost == null) throw new ArgumentNullException("traversalCost");
            Hint = hint;
            TraversalCost = traversalCost;
            TotalNodeCount = totalNodeCount;
        }

        protected readonly NearbyNodesHint Hint;
        protected readonly InternodeTraversalCost TraversalCost;
        protected readonly int TotalNodeCount;

        public struct Results
        {
            /// <summary> 
            /// Prepares a Dijkstra results package. 
            /// </summary> 
            /// <param name="minimumPath"> 
            /// The minimum path array, where each array element index corresponds  
            /// to a node designation, and the array element value is a pointer to 
            /// the node that should be used to travel to this one. 
            /// </param> 
            /// <param name="minimumDistance"> 
            /// The minimum distance from the starting node to the given node. 
            /// </param> 
            public Results(int[] minimumPath, float[] minimumDistance)
            {
                MinimumDistance = minimumDistance;
                MinimumPath = minimumPath;
            }

            /// The minimum path array, where each array element index corresponds  
            /// to a node designation, and the array element value is a pointer to 
            /// the node that should be used to travel to this one. 
            public readonly int[] MinimumPath;

            /// The minimum distance from the starting node to the given node. 
            public readonly float[] MinimumDistance;
        }

        public class QueueElement : IComparable
        {
            public int index;
            public float weight;

            public QueueElement() { }
            public QueueElement(int i, float val)
            {
                index = i;
                weight = val;
            }

            public int CompareTo(object obj)
            {
                QueueElement outer = (QueueElement)obj;

                if (this.weight > outer.weight)
                    return 1;
                else if (this.weight < outer.weight)
                    return -1;
                else return 0;
            }
        }


        // start: The node to use as a starting location. 
        // A struct containing both the minimum distance and minimum path 
        // to every node from the given <paramref name="start"/> node. 
        public virtual Results Perform(int start)
        {
            // Initialize the distance to every node from the starting node. 
            float[] d = GetStartingTraversalCost(start);
            distance = new float[d.Length];
            // Initialize best path to every node as from the starting node. 
            int[] p = GetStartingBestPath(start);
            BasicHeap Q = new BasicHeap();
            //FastHeap Q = new FastHeap(TotalNodeCount);

            for (int i = 0; i != TotalNodeCount; i++)
                Q.Push(i, d[i]);

            while (Q.Count != 0)
            {
                int v = Q.Pop();
                foreach (int w in Hint(v))
                {
                    if (w < 0 || w > Q.Count - 1) continue;

                    float cost = TraversalCost(v, w);
                    if (cost < float.MaxValue && d[v] + cost < d[w]) // don't let wrap-around negatives slip by 
                    {
                        // We have found a better way to get at relative 
                        d[w] = d[v] + cost; // record new distance 
                        distance[w] = d[v] + cost;
                        p[w] = v;
                        Q.Push(w, d[w]);
                    }
                }
            }
            
            return new Results(p, d);
        }

        // start: The node to use as a starting location. 
        // A struct containing both the minimum distance and minimum path 
        // to every node from the given <paramref name="start"/> node. 
        public virtual Results Perform2(int start)
        {
            // Initialize the distance to every node from the starting node. 
            float[] d = GetStartingTraversalCost(start);

            // Initialize best path to every node as from the starting node. 
            int[] p = GetStartingBestPath(start);
            BinaryPriorityQueue Q = new BinaryPriorityQueue();

            for (int i = 0; i != TotalNodeCount; i++)
                Q.Push(new QueueElement(i, d[i]));

            while (Q.Count != 0)
            {
                int v = ((QueueElement)Q.Pop()).index;

                foreach (int w in Hint(v))
                {
                    if (w < 0 || w > Q.Count - 1) continue;

                    float cost = TraversalCost(v, w);
                    if (cost < float.MaxValue && d[v] + cost < d[w]) // don't let wrap-around negatives slip by 
                    {
                        // We have found a better way to get at relative 
                        d[w] = d[v] + cost; // record new distance 
                        p[w] = v;
                        Q.Push(new QueueElement(w, d[w]));
                    }
                }
            }

            return new Results(p, d);
        }

        // Uses the Dijkstra algorithhm to find the minimum path 
        // from one node to another. 
        // Return a struct containing both the minimum distance and minimum path 
        // to every node from the given start node. 
        public virtual int[] GetMinimumPath(int start, int finish)
        {
            if (start < finish)
            {
                int tmp = start;
                start = finish;
                finish = tmp;
            }

            Results results = Perform(start);
            return GetMinimumPath(start, finish, results.MinimumPath);
        }

        // Finds an array of nodes that provide the shortest path 
        // from one given node to another. 
        // ShortestPath : P array of the completed algorithm:
        // The list of nodes that provide the one step at a time path from 
        protected virtual int[] GetMinimumPath(int start, int finish, int[] shortestPath)
        {
            Stack<int> path = new Stack<int>();

            do
            {
                path.Push(finish);
                finish = shortestPath[finish]; // step back one step toward the start point 
            }
            while (finish != start);
            return path.ToArray();
        }

        // Initializes the P array for the algorithm. 
        // A fresh P array will set every single node's source node to be  
        // the starting node, including the starting node itself. 
        protected virtual int[] GetStartingBestPath(int startingNode)
        {
            int[] p = new int[TotalNodeCount];
            for (int i = 0; i < p.Length; i++)
                p[i] = startingNode;
            return p;
        }

        // Initializes the D array for the start of the algorithm.
        // The traversal cost for every node will be set to impossible 
        // (int.MaxValue) unless a connecting edge is found between the 
        // starting node and the node in question.
        protected virtual float[] GetStartingTraversalCost(int start)
        {
            float[] subset = new float[TotalNodeCount];
            for (int i = 0; i != subset.Length; i++)
                subset[i] = float.MaxValue; // all are unreachable 
            subset[start] = 0; // zero cost from start to start 
            foreach (int nearby in Hint(start))
                subset[nearby] = TraversalCost(start, nearby);
            return subset;
        }

    }
    class Blockage
    {
        public int U;
        public int V;

        public Blockage(int u, int v)
        {
            U = u;
            V = v;
        }
    }
 

  
   

}


 
    

